package creative.fire.interview.amazon;

import java.util.Stack;

/**
 * Constriants: 1. getMinimum should return the minimum value in O(1) 2. Space constraint also
 * has to be considered while designing it and if you use extra space, it should be of constant
 * space.
 * 
 * @author Administrator
 * @param <T>
 * http://stackoverflow.com/questions/tagged/interview-questions+java
 */
public class FastMinStack<T extends Comparable<T>> {
	private final Stack<T> stack = new Stack<T>();
	private T minimum;

	public void push(T element) {
		if (stack.size() == 0 || element.compareTo(minimum) <= 0) {
			stack.push(minimum);
			stack.push(element);
			minimum = element;
		} else {
			stack.push(element);
		}
	}

	public T pop() {
		T element = stack.pop();
		if (element.compareTo(minimum) == 0) {
			minimum = stack.pop();
		}
		return element;
	}

	public T getMinimum() {
		return minimum;
	}

	public static void main(String[] args) {
		FastMinStack<Integer> myStack = new FastMinStack<Integer>();
		myStack.push(4);//2
		printMinimum(myStack);
		myStack.push(3);//2 3
		printMinimum(myStack);
		myStack.push(2);//2 3 1
		printMinimum(myStack);
		myStack.push(1);//2 3 1 4
		printMinimum(myStack);
		myStack.pop();//2 3 1
		printMinimum(myStack);
		myStack.pop();//2 3
		printMinimum(myStack);
		myStack.pop();//2
		printMinimum(myStack);
		
		myStack.pop();//2
		printMinimum(myStack);
		myStack.pop();//2
		printMinimum(myStack);
	}

	private static void printMinimum(FastMinStack<Integer> myStack) {
		Integer min;
		min = myStack.getMinimum();
		System.out.println(min);
	}
}